#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>

using namespace std;
#define MAXN 130
#define INF 0x3f3f3f3f

int n, m;
int p[MAXN];
int f[(1<<11)+5][(1<<11)+5];

int dfs(int s1, int s2)
{
	if (f[s1][s2] != INF)
		return f[s1][s2];
	int cnt = 0;
	for(int i = 0; i < n; ++ i)
	{
		if ( (p[i] & s1) == s2)
			++ cnt;
	}
	
	if (cnt <= 1)
	{
		f[s1][s2] = 0;
		return 0;
	}
	
	for(int i = 0; i < m; ++ i)
	{
		if (s1 & (1<<i) )
			continue;
		int nextQuestion = s1 | (1<<i);
		int &d = f[s1][s2];
		d = min(d, max(dfs(nextQuestion, s2), dfs(nextQuestion, s2^(1<<i))) + 1);
	}
	return f[s1][s2];
}


int main(int argc, char * argv[])
{
	char str[MAXN];
	for(; scanf("%d%d", &m, &n) != EOF && n + m;)
	{
		for(int i = 0; i < n; i ++)
		{
			scanf("%s", &str);
			p[i] = 0;
			for (int j = 0; str[j]; j ++)
			{
				p[i] |= (str[j] - '0')<<j;
			}
		}
		memset(f, 0x3f, sizeof(f));
		printf("%d\n", dfs(0, 0));
	}
	return 0;
}
